\documentclass{beamer}
\usepackage{ctex}
\usepackage{xcolor}
\usetheme{Madrid}

\author{uncle-lu}
\institute{乌鲁木齐市第一中学}
\title{NOIP2015Day2 解析报告}
\date{\today}

\begin{document}
\frame{\titlepage}

\section{概述}

\begin{frame}\frametitle{概述}
	\begin{itemize}
		\item 1\quad 跳石子
		\item 2\quad 子串
		\item 3\quad 运输计划
	\end{itemize}

	\pause

	个人觉得NOIP2015Day2难度总体上来比Day1难很多.

	这个很符合基本法.

	但是两试难度差别也太大了.

	\pause

	比如说讲Day1的 dalao 他准备那节课准备了一下午.

	\pause

	而我这个蒟蒻准备今天这节课准备了将近1天.

	\pause

	当然这里面也有 他太强.我太弱的原因.
\end{frame}

\section{第一题}

\begin{frame}\frametitle{第一题}
	\begin{beamerboxesrounded}[shadow=true]{\textbf{题目概述:}}
		给一些距离.然后让你去掉那些石子.使得距离\textbf{最小值最大}.
	\end{beamerboxesrounded}
	对于20$\%$\quad$0\leq N\leq 10$

	对于50$\%$\quad$0\leq N\leq 100$

	对于100$\%$\quad$0 \leq N\leq 50000 \quad 0\leq L\leq 1000000000$
\end{frame}

\subsection{分析}

\begin{frame}\frametitle{分析}
	20\% 的点 允许的复杂度有很多 \quad 个人认为上限 $O(2^n)$

	\pause

	50\% 的点 允许的复杂度也有很多 $O(n^2)$ ? $O(n^3)$ ? 

	\pause

	100\%的点 诶?这个L怎么这么大.\pause 你应该很快想到这个复杂度里可能有$log$
\end{frame}

\subsection{算法一}

\begin{frame}\frametitle{算法一}
	对于20\%的点.我们可以枚举每个石子的状态.

	\pause

	\begin{block}{Tags1:}
		求最值问题可转化为:枚举然后转成判断性问题.
	\end{block}

	\pause

	算法复杂度$O(2^n)$

	预计得分: 20分
\end{frame}

\subsection{算法二}

\begin{frame}\frametitle{算法二}
	我们需要再看一下题面.

	\pause

	\textbf{最小值最大}

	\pause

	\begin{block}{Tags2:}
		最小值最大或者最大值最小.一般都可以用二分来解决.
	\end{block}

	这又是将最值问题转换成判断性问题的一个方法.\textbf{二分}

	\pause
\end{frame}

\begin{frame}\frametitle{算法二}
	\begin{itemize}
		\item 首先二分答案.
		\item 之后用二分出的答案去判断.
			\begin{itemize}
				\item 除去的石头有几个.
				\item 该值是否合法.
			\end{itemize}
		\item 输出
	\end{itemize}

	\pause

	算法复杂度:$O(n\cdot logL)$

	算法预计得分:100分
\end{frame}

\section{第二题}

\begin{frame}\frametitle{第二题}
	\begin{block}{\textbf{题目概述}}
		给你两个串.让你从第一个串取出k个不重叠的子串,使得这些子串组成一个新串.新串与第二个串相等.问你有多少组满足要求的第一个串的子串.
	\end{block}
	对于第 1 组数据:$1\leq n\leq 500,1\leq m\leq 50,k=1;$

	对于第 2 组至第 3 组数据:$1\leq n\leq 500,1\leq m\leq 50,k=2;$

	对于第 4 组至第 5 组数据:$1\leq n\leq 500,1\leq m\leq 50,k=m;$

	对于第 1 组至第 7 组数据:$1\leq n\leq 500,1\leq m\leq 50,1\leq k\leq m$

	对于第 1 组至第 9 组数据:$1\leq n\leq 1000,1\leq m\leq 100,1\leq k\leq m$

	对于所有 10 组数据:$1\leq n\leq 1000,1\leq m\leq 200,1\leq k\leq m.$
\end{frame}

\begin{frame}\frametitle{分析}
	我们发现这道题的数据点有些特点.
	\pause

	前5个点k的值是固定的.

	\pause

	而后面的点n不是很大.
\end{frame}

\begin{frame}\frametitle{算法一}
	对于第一组数据.我们发现可以直接用第二个串匹配第一个串.

	\pause

	算法复杂度$O($不正确$)$
	\pause
	其实是$O(n^2)$

	算法预计得分10分.
\end{frame}

\begin{frame}\frametitle{算法二}

	对于第二至第三组数据.

	我们可以枚举第二个子串的中间节点.

	然后用第二个子串的前部分去匹配.匹配到了再用后半部分去匹.

	\pause

	算法复杂度$O(n^4)$
\end{frame}

\begin{frame}\frametitle{算法三}
	这道题看起来又要分块又要匹配.

	应该很容易就能想到这是一道动态规划题.

	所以我们接下来考虑一下状态和转移.

\end{frame}

\begin{frame}\frametitle{从零构思动态规划}
	从初始状态转移至最末状态.
	\pause

	初始状态为:A串与B串都没有匹配.

	最末状态为:A串n个与B串m个分别分组了k组.

	\pause

	所以我们在设计状态的时候需要设计以下几个关键元素:
	\begin{itemize}
			\pause
		\item A串匹配到的位置.
			\pause
		\item A串分的组.
			\pause
		\item B串匹配到的位置.
	\end{itemize}

\end{frame}

\begin{frame}\frametitle{从零构思动态规划(伪)}
	我们设\(F_{i,j,k}\)表示第A串匹配到i位.第B串匹配到j位.A串分了K组.的情况数.
	\pause
	
	我们一共会有几种情况?\pause 2种.
\end{frame}

\begin{frame}\frametitle{分析动态规划的转移?}
	情况1:
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.5\textwidth]{DP1.png}
	\end{figure}
\end{frame}
\begin{frame}\frametitle{分析动态规划的转移!}
	情况2:
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.5\textwidth]{DP2.png}
	\end{figure}
	\pause
	所以我们发现如果当前为\(F_{i,j,k}\)这与\(\sum_{x=1}^{i-1} F_{x,j-1,k-1}\)和\(F_{i-1,j-1,k}\)有关
\end{frame}

\begin{frame}\frametitle{算法三}
	所以我们的转移就变成了
	\[
		F_{i,j,k}=\left\{\!\!\!
			\begin{array}{ll}
				\sum_{x=1}^{i-1} F_{x,j-1,k-1} + F_{i-1,j-1,k} & \text{A[i]==B[j]}\\
				0 & \text{A[i]!=B[j]}
			\end{array}\right.
	\]
\end{frame}

\begin{frame}\frametitle{算法三}
	所以我们最后再用前缀和优化一下\[\sum_{x=1}^{i-1} F_{x,j-1,k-1}\]

	

\end{frame}

\section{第三题}

\begin{frame}\frametitle{第三题}
	\begin{block}{题目概述}
		给你一棵树.然后每条边都有权值.之后给你m条路径.让你将树上的一条边权值变为0.使得这些最长路径最小.
	\end{block}
\end{frame}

\begin{frame}\frametitle{数据点}
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.75\textwidth]{First.png}
	\end{figure}
\end{frame}

\subsection{分析}

\begin{frame}\frametitle{分析}
	喜闻乐见的图论题.

	\begin{block}{Tags3}

		一道图论题拿到手.我们需要将其中的内部模型抽象出来.想题之前应该将所学过的相对应的算法罗列一下.

		\pause
		这样在处理问题的时候,就会有一定的解决问题的想法.

	\end{block}

	\pause

	讲了那么多的算法.我们罗列一下我们拿上题需要想的几个方向.

	\pause

	\begin{itemize}
		\item 复杂度高的算法
		\item 优化复杂度高的算法
		\item 不正确的算法
		\item 是否可以将不正确的算法.修改成正确的算法.
		\item 正解算法
		\item 优化过的正解算法
	\end{itemize}

\end{frame}

\subsection{算法}

\begin{frame}
	\begin{center}
		\LARGE\textbf{认真读数据}
	\end{center}
\end{frame}

\begin{frame}\frametitle{算法一}
	不正确的算法一.

	通过读数据我们发现这之间有一些$m=1$的数据点.

	\pause

	$\because\quad m=1$
	$\therefore $我们只需要统计这一条航道上的最大值.

	算法复杂度$O(nlogn)$

	算法预计得分:20分.
\end{frame}

\begin{frame}\frametitle{细节一}

	如果计算树上路径最大值?

	\pause

	树上倍增找LCA.

\end{frame}

\begin{frame}\frametitle{猜想二}
	算法二我本来是要放正解的.但是我想口胡一个错误的猜想.

	\pause

	多想是件好事情.但是在考试的时候且行且珍惜.
\end{frame}

\begin{frame}\frametitle{算法三}
	算法三我们来讲正解.

	我们从新阅览一遍题目可发现这道题其实在求.\textbf{运输计划的最大时间最小}.

	\pause

	所以我们可以用二分来确定答案?

	\pause

	所以我们需要思考:

	\begin{itemize}
		\item 二分什么.
		\item 我们怎么判断答案.
	\end{itemize}
\end{frame}

\begin{frame}\frametitle{算法三}
	我们二分一个$t$.代表所有运输计划的最大时间.所以我们需要预处理出来所有的路径的时间.

	\pause

	之后如果时间比t小我们不去管.时间如果比t大.我们需要求一个所有比t大的路径的交集.然后在这个交集里删去最大值.再看与t的关系
\end{frame}

\begin{frame}\frametitle{细节一}
	我们怎么求比t大的路径的交集呢?
\end{frame}

\begin{frame}\frametitle{细节一}
	我们简化一下问题.

	如果在一个线性的序列中.我们需要快速记录一些区间被记录的次数.离线操作.最后查询.

	如果一个区间为$[a,b)$我们可以将这个序列中$Sum[a]+1$将这个序列中$Sum[b]-1$
	\begin{figure}[htbp]
		\centering
		\includegraphics[width=0.75\textwidth]{Secend.png}
	\end{figure}

	之后再算一遍前缀和.$Sum_i = \sum_1^i V_i$.

	\begin{figure}[htbp]
		\centering
		\includegraphics[width=1\textwidth]{Third.png}
	\end{figure}

\end{frame}

\begin{frame}\frametitle{算法三}
	然后我们将这种用法推展到树上.

	\[ S_i = \sum_{k \in son(i)} V_k\]

	\pause

	对于路径的两个节点A,B
	我们需要修改的就是 \(S_A,S_B,S_{lca(A,B)}\)

	之后我们就可以算出每条边的使用次数.之后在交集中求出最大值来判断
\end{frame}

\begin{frame}\frametitle{算法三}
	所以总结一下

	\begin{itemize}
		\item 首先得预处理树上距离.
		\item 首先用二分来暴力找答案
		\item 在二分的时候用前缀和树上差分来判断答案正确性.
	\end{itemize}

	\pause

	如果您还是没有懂.

	https://blog.sengxian.com/solutions/noip-2015-day2

	这是我在网上找的正解的博客.

	这个博客里还有第二种求交集的办法.但是太暴力不建议大家写QwQ.

	\pause

	算法高于实现.

	所以希望我讲完大家明白这个算法是什么样的.实现是在完全理解算法之后,顺理成章的事情.

\end{frame}

\begin{frame}\frametitle{总结一下}
	总结一下NOIP2015Day2
	\pause
	\begin{itemize}
		\item 整体题比较难.所以在Day1如此简单的错觉下.需要扇自己一巴掌.让自己保持清醒.
			\pause
		\item 拿到大型图论或者是数据结构题.需要梳理结构类型.然后梳理所学过的解决问题的方法.
			\pause
		\item 需要有好的心态面临爆0.
			\pause
		\item 不能确定正确性的尽量少花时间来费在实现上.
	\end{itemize}
\end{frame}

\begin{frame}\frametitle{结束}
	以上为全部内容.

	讲课人:uncle-lu

	博客:uncle-lu.org

	本次讲课资料(包括源码):https://gitee.com/uncle-lu/Tex-Doc

	Bilibili直播间:https://live.bilibili.com/1269934
\end{frame}

\end{document}
